
#[derive(Debug, PartialEq, Eq)]
enum Cons<T: Clone> {
  Cons(T, Box<Cons<T>>),
  Null
}

impl<T: Clone> Cons<T> {
  pub fn new(head: T, tail: Self) -> Self {
    Cons::Cons(head, Box::new(tail))
  }

  pub fn to_vec(&self) -> Vec<T> {
    match self {
      &Cons::Null => vec![],
      &Cons::Cons(ref head, ref tail) => {
        let mut head = vec![head.clone()];
        head.extend(tail.to_vec());
        head
      }
    }
  }
}

impl<T: Clone> Cons<T> {
  pub fn from_iter<I>(it: I) -> Self
    where I: IntoIterator<Item=T>, <I as IntoIterator>::IntoIter: DoubleEndedIterator
  {
    //TODO: provide a convenient method to convert any iterable
    //      to an algebraic list.
    let mut cons = Cons::Null;
    let mut it_iter = it.into_iter().rev();
    while let Some(x) = it_iter.next() {
        cons = Cons::new(x, cons);
    }
    cons
  }

  pub fn filter<F>(&self, fun: F) -> Self
    where F: Fn(&T) -> bool
  {
    //TODO: return a new algebraic list containing only elements
    //      that satisfy the predicate function.
    Cons::from_iter(
        self.to_vec().iter().filter(|x| fun(x))
        .map(|x| x.clone())
    )
  }

  pub fn map<F,S>(&self, fun: F) -> Cons<S>
    where F: Fn(T) -> S, S: Clone
  {
    //TODO: return a new algebraic list containing all elements
    //      resulting from applying the mapper function to them.
    Cons::from_iter(self.to_vec().iter().map(|x| fun(x.clone())))
  }
}